#include "TopologicalSort.h"

/**
 * @brief 求顶点的入度
 * @param ALGraph G 图G（邻接表存储结构）
 * @param int indegree[] 存储顶点入度的数组 就是指向它的点的数目
 * @retval 无
 */
void FindInDegree(ALGraph G, int *indegree) {

  ArcNode *p;

  //对存储入度的indegree数组赋初值0
  for (int i = 0; i < G.vexnum; i++) {
    indegree[i] = 0;
  } // for

  for (int i = 0; i < G.vexnum; i++) {

    // p指向顶点i后面弧链表的首元结点  首元节点(存储第一个数据元素的节点)
    p = G.vertices[i].firstarc;
    while (p) {
      indegree[p->data.adjvex]++;
      p = p->nextarc;
    } // while
  }   // for
} // FindInDegree

/**
 * @brief 若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR
 * @param ALGraph G 有向图G（邻接表存储结构）有向图是单一的且没有权值
 * @retval 状态码，操作成功返回OK，操作失败返回ERROR
 */
Status TopologicalSort(ALGraph G) {

  int i, k, count = 0;          // count为已输出顶点数,初始值为0
  int indegree[MAX_VERTEX_NUM]; //入度数组
  Stack S;
  ArcNode *p;

  FindInDegree(G, indegree);
  InitStack(S); //栈有倒序的作用

  for (i = 0; i < G.vexnum; i++) {

    //若其入度为0，则将i压入零入度顶点栈S
    if (!indegree[i]) {
      Push(S, i);
    } // if
  }   // for

  //零入度栈顶站S不空  为空就不会循环了
  while (!StackIsEmpty(S)) {
    Pop(S, i); //从栈中弹出一个零入度顶点的序号，并将其保存到i
    printf(" %d ", G.vertices[i].data);
    ++count;

    for (p = G.vertices[i].firstarc; p; p = p->nextarc) {

      // i号顶点的邻接点序号为k
      k = p->data.adjvex;

      if (!(--indegree[k])) { //只有当--indegree[k] 为0时有Push操作
        Push(S, k);           //
      }                       // if
    }                         // for
  }                           // while

  if (count < G.vexnum) {
    printf("此有向图有回路\n");
    return ERROR;
  } else {
    return OK;
  } // else
} // TopologicalSort